A computer-aided design (CAD) system should account for the dynamic nature of the design process, enabling design modifications while recognizing critical design constraints which should not change. In the past, it was necessary for the CAD engineer to remember the design constraints and relationships and consciously preserve them every time a change is made to the design, increasing both design time and the possibility of error. Maintaining design constraints and relationships is particularly difficult through multiple design changes, particularly with complex pans. Compounding the problem is the fact that even simple designs include hundreds of constraints and all of the design constraints may not be known when a modification is made or attempted. Ideally, a CAD system would allow the engineer to make a design change while maintaining critical constraints, would identify conflicts among the constraints, and possible solutions where the design is over-constrained.
Many design problems can be generally described as constraint satisfaction problems. That is, given a collection of entities and constraints that describe how the entities react and relate to each other, find a configuration of the system so as to satisfy all constraints simultaneously. U.S. Pat. No. 5,452,238 (incorporated by reference) describes a method for finding the possible configurations of a geometric system having a collection of geometric entities that satisfy a set of geometric constraints. U.S. Pat. No. 5,452,238 forms a basis for a geometric constraint engine (GCE) used in a sketching product under development.
GCE finds positions, orientations and dimensions of geometric entities in 3D that satisfy a set of constraints relating different entity features. Geometric entities can be nested hierarchically in a part-whole relationship; aggregate entities are composed of combinations of primitive ones--points, vectors and dimensions.
With the exception of dimensional constraints, all constraints used in GCE are binary constraints--they relate two geometric entities. These constraints may additionally involve real parameters. Examples of constraints used in GCE are shown in Table 1. Dimensional constraints are unary; they relate one geometric entity to a real-valued dimension parameter. Constraints may apply to subparts of a given entity. For example, to constrain two lines to be parallel one constrains the vectors of those lines to have an angle of zero.
TABLE 1 ______________________________________ Constraints used in GCE Constraint name Explanation ______________________________________ dist:point-point(G.sub.l,G.sub.2,d) Distance between point G.sub.1 and point G.sub.2 is d. dist:point-line(G.sub.1,G.sub.2,d) Distance between point G.sub.1 and line G.sub.2 is d. dist:point-plane(G.sub.1,G.sub.2,d) Distance between point G.sub.1 and plane G.sub.2 is d. dist:line-circle(G.sub.1,G.sub.2,d) Distance between line G.sub.1 and circle G.sub.2 is d..sup.a angle:vec-vec(G.sub.1,G.sub.2,.alpha.) Angle between vector G.sub.1 and vector G.sub.2 is a. ______________________________________ .sup.a. In two dimensions, d = 0 represents a tangency constraint.
GCE addresses an issue currently outside the major focus of constraint-based systems research: solving highly nonlinear constraint problems over the domain of real numbers. To solve these problems, GCE imposes an operational semantics for constraint satisfaction in the geometry domain. It does so by employing a metaphor of incremental assembly; geometric entities are moved to satisfy constraints in an incremental manner. The assembly process is virtual, as geometric entities are treated as ghost objects that can pass through each other during assembly. Such an assumption is allowed because the goal of the constraint satisfaction process is to determine globally-consistent locations of the geometric entities rather than the paths required for a physical assembly of that geometry.
GCE assembles geometric entities incrementally to satisfy the constraints acting on them. As the objects are assembled, their degrees of freedom are consumed by the constraints, and geometric invariants are imposed. An operational semantics is imposed: measurements and actions are used to satisfy each individual constraint. GCE uses information about an entity's degrees of freedom to decide which constraint to solve and to ensure that an action being applied to a geometric entity does not invalidate any geometric invariants imposed by previously-satisfied constraints. This ensures that the solution method is confluent.
GCE can handle fully- as well as under- and over-constrained models. The solution of a set of constraints can be captured as a plan that may be replayed to satisfy the constraints when one or more numerical constraint parameters are changed.
In the GCE context, a constraint model is fully constrained when there are no remaining degrees of freedom after all constraints have been satisfied, and where no constraint in the system is redundant. The constraint model is under-constrained when there are remaining degrees of freedom in the model. Over-constrained models result from adding more constraints to a fully constrained model (or by adding a constraint restricting M degrees of freedom to a model with N remaining degrees of freedom, where M is greater than N).
For a further description of GCE and the use of geometric constraints in kinematics and conceptual design, see, Glenn Kramer, "Solving geometric constraint systems," In Proceedings of the 8th National Conference on Artificial Intelligence, pages 708-714, Boston, Mass., August 1990, American Association for Artificial Intelligence, MIT Press; Jahir Pabon, Robert Young, and Walid Keirouz, "Integrating parametric geometry, features, and variational modeling for conceptual design," Systems Automation: Research and Applications, 2:17-36, 1992; Glenn Kramer, "Solving Geometric Constraint Systems: A Case Study in Kinematics," MIT Press, Cambridge, Mass., 1992; Glenn Kramer, "A geometric constraint engine," Artificial Intelligence, 58:327-360, December 1992 (all incorporated by reference for background).
For many real world design problems, it is important to identify and remove a constraint from the over-constrained model so that solution is possible. Further, the designer may want to explore the effects on the model if different constraints are removed or the parameters of a constraint are changed. A method for identifying the set of constraints over-constraining a model and assisting the designer in removing or changing a constraint from the set and analyzing the effect on the system would be a significant aid in evaluating a constraint satisfaction problem.